/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        567.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/9 13:56
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
//
//换句话说，第一个字符串的排列之一是第二个字符串的子串。
#include "../header.h"

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        unordered_map<char, int> gap; // 正数表示还需出现的次数，负数表示多出现的次数，0表示正好
        for (char c : s1)
            gap[c]++;
        int left = 0, right = 0;// [left,right)
        while (right < s2.size()) {
            char c = s2[right++];
            gap[c]--; //入窗
            while (left < right && gap[c] < 0){
                gap[s2[left++]]++; // 直到gap[c]==0
            }
            if (right - left == s1.size())
                return true;
        }
        return false;
    }
};